{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Open the Lock"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: openLock"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #打开转盘锁"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： <code>'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'</code> 。每个拨轮可以自由旋转：例如把 <code>'9'</code> 变为&nbsp;<code>'0'</code>，<code>'0'</code> 变为 <code>'9'</code> 。每次旋转都只能旋转一个拨轮的一位数字。</p>\n",
    "\n",
    "<p>锁的初始数字为 <code>'0000'</code> ，一个代表四个拨轮的数字的字符串。</p>\n",
    "\n",
    "<p>列表 <code>deadends</code> 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。</p>\n",
    "\n",
    "<p>字符串 <code>target</code> 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>deadends = [\"0201\",\"0101\",\"0102\",\"1212\",\"2002\"], target = \"0202\"\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "可能的移动序列为 \"0000\" -&gt; \"1000\" -&gt; \"1100\" -&gt; \"1200\" -&gt; \"1201\" -&gt; \"1202\" -&gt; \"0202\"。\n",
    "注意 \"0000\" -&gt; \"0001\" -&gt; \"0002\" -&gt; \"0102\" -&gt; \"0202\" 这样的序列是不能解锁的，\n",
    "因为当拨动到 \"0102\" 时这个锁就会被锁定。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> deadends = [\"8888\"], target = \"0009\"\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>把最后一位反向旋转一次即可 \"0000\" -&gt; \"0009\"。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> deadends = [\"8887\",\"8889\",\"8878\",\"8898\",\"8788\",\"8988\",\"7888\",\"9888\"], target = \"8888\"\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>无法旋转到目标数字且不被锁定。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;=&nbsp;deadends.length &lt;= 500</code></li>\n",
    "\t<li><code><font face=\"monospace\">deadends[i].length == 4</font></code></li>\n",
    "\t<li><code><font face=\"monospace\">target.length == 4</font></code></li>\n",
    "\t<li><code>target</code> <strong>不在</strong> <code>deadends</code> 之中</li>\n",
    "\t<li><code>target</code> 和 <code>deadends[i]</code> 仅由若干位数字组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [open-the-lock](https://leetcode.cn/problems/open-the-lock/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [open-the-lock](https://leetcode.cn/problems/open-the-lock/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"0201\",\"0101\",\"0102\",\"1212\",\"2002\"]\\n\"0202\"', '[\"8888\"]\\n\"0009\"', '[\"8887\",\"8889\",\"8878\",\"8898\",\"8788\",\"8988\",\"7888\",\"9888\"]\\n\"8888\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        dead = set(deadends)\n",
    "        visited = set()\n",
    "        q = deque()\n",
    "        step = 0\n",
    "\n",
    "        q.append(\"0000\")\n",
    "        visited.add(\"0000\")\n",
    "        \n",
    "        while len(q) != 0:\n",
    "            size = len(q)\n",
    "            for _ in range(size):\n",
    "                cur = q.popleft()\n",
    "\n",
    "                if cur in dead:\n",
    "                    continue\n",
    "                if cur == target:\n",
    "                    return step\n",
    "                for i in range(4):\n",
    "                    up = self.flip_up(cur, i)\n",
    "                    if up not in visited:\n",
    "                        visited.add(up)\n",
    "                        q.append(up)\n",
    "                    down = self.flip_down(cur, i)\n",
    "                    if down not in visited:\n",
    "                        visited.add(down)\n",
    "                        q.append(down)\n",
    "            step += 1\n",
    "        return -1\n",
    "    def flip_up(self, s, i):\n",
    "        s = list(s)\n",
    "        if s[i] == \"9\":\n",
    "            s[i] = \"0\"\n",
    "        else:\n",
    "            s[i] = str(int(s[i]) + 1)\n",
    "        return \"\".join(s)\n",
    "    def flip_down(self, s, i):\n",
    "        s = list(s)\n",
    "        if s[i] == \"0\":\n",
    "            s[i] = \"9\"\n",
    "        else:\n",
    "            s[i] = str(int(s[i]) - 1)\n",
    "        return \"\".join(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        # 查看是否有解 ####\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "\n",
    "        lst = []\n",
    "        for i, n in enumerate(list(target)):\n",
    "            b = list(target)\n",
    "            if n == \"9\":\n",
    "                b[i] = \"0\"\n",
    "            else:\n",
    "                b[i] = str(int(n) + 1)\n",
    "            c = \"\".join(b)\n",
    "            lst.append(c)\n",
    "            if n == \"0\":\n",
    "                b[i] = \"9\"\n",
    "            else:\n",
    "                b[i] = str(int(n) - 1)\n",
    "            c = \"\".join(b)\n",
    "            lst.append(c)\n",
    "\n",
    "        dead_flag = True\n",
    "        for i in lst:\n",
    "            if i not in deadends:\n",
    "                dead_flag = False\n",
    "                break\n",
    "        if dead_flag:\n",
    "            return -1\n",
    "        ###########\n",
    "\n",
    "        # 计算最小步数\n",
    "        num = 0\n",
    "        for i, n in enumerate(target):\n",
    "            if int(n) > 5:\n",
    "                num += (10 - int(n))\n",
    "            else:\n",
    "                num += int(n)\n",
    "\n",
    "        # 查看是否能够使用最小步数\n",
    "        lst2 = set()\n",
    "        for i, n in enumerate(list(target)):\n",
    "            b = list(target)\n",
    "            if int(n) > 5:\n",
    "                if n == \"9\":\n",
    "                    b[i] = \"0\"\n",
    "                else:\n",
    "                    b[i] = str(int(n) + 1)\n",
    "            else:\n",
    "                if n == \"0\":\n",
    "                    b[i] = \"0\"\n",
    "                else:\n",
    "                    b[i] = str(int(n) - 1)\n",
    "            c = \"\".join(b)\n",
    "            lst2.add(c)\n",
    "\n",
    "        if target in lst2:\n",
    "            lst2.remove(target)\n",
    "\n",
    "        min_flag = False\n",
    "        for i in lst2:\n",
    "            if i not in deadends:\n",
    "                min_flag = True\n",
    "                break\n",
    "\n",
    "        return num if min_flag else num + 2\n",
    "                \n",
    "                \n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack, result, dp = [\"0000\"], 0, [1] * 10000\n",
    "        for dead in deadends:\n",
    "            dp[1000 * int(dead[0]) + 100 * int(dead[1]) + 10 * int(dead[2]) + int(dead[3])] = 0\n",
    "        if not dp[0]:\n",
    "            if target == \"0000\":\n",
    "                return 0\n",
    "            return -1\n",
    "        dp[0] = 0\n",
    "        while stack:\n",
    "            temp = []\n",
    "            for item in stack:\n",
    "                if item == target:\n",
    "                    return result\n",
    "                cur = 1000 * int(item[0]) + 100 * int(item[1]) + 10 * int(item[2]) + int(item[3])\n",
    "                for i in range(4):\n",
    "                    x = cur - 10 ** i if item[-i - 1] != \"0\" else cur + 9 * 10 ** i\n",
    "                    y = cur + 10 ** i if item[-i - 1] != \"9\" else cur - 9 * 10 ** i\n",
    "                    if dp[x]:\n",
    "                        dp[x] -= 1\n",
    "                        x = str(x)\n",
    "                        temp.append(\"0\" * (4 - len(x)) + x)\n",
    "                    if dp[y]:\n",
    "                        dp[y] -= 1\n",
    "                        y = str(y)\n",
    "                        temp.append(\"0\" * (4 - len(y)) + y)\n",
    "            stack = temp[:]\n",
    "            result += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        # 查看是否有解 ####\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "\n",
    "        lst = []\n",
    "        for i, n in enumerate(list(target)):\n",
    "            b = list(target)\n",
    "            if n == \"9\":\n",
    "                b[i] = \"0\"\n",
    "            else:\n",
    "                b[i] = str(int(n) + 1)\n",
    "            c = \"\".join(b)\n",
    "            lst.append(c)\n",
    "            if n == \"0\":\n",
    "                b[i] = \"9\"\n",
    "            else:\n",
    "                b[i] = str(int(n) - 1)\n",
    "            c = \"\".join(b)\n",
    "            lst.append(c)\n",
    "\n",
    "        dead_flag = True\n",
    "        for i in lst:\n",
    "            if i not in deadends:\n",
    "                dead_flag = False\n",
    "                break\n",
    "        if dead_flag:\n",
    "            return -1\n",
    "        ###########\n",
    "\n",
    "        # 计算最小步数\n",
    "        num = 0\n",
    "        for i, n in enumerate(target):\n",
    "            if int(n) > 5:\n",
    "                num += (10 - int(n))\n",
    "            else:\n",
    "                num += int(n)\n",
    "\n",
    "        # 查看是否能够使用最小步数\n",
    "        lst2 = set()\n",
    "        for i, n in enumerate(list(target)):\n",
    "            b = list(target)\n",
    "            if int(n) > 5:\n",
    "                if n == \"9\":\n",
    "                    b[i] = \"0\"\n",
    "                else:\n",
    "                    b[i] = str(int(n) + 1)\n",
    "            else:\n",
    "                if n == \"0\":\n",
    "                    b[i] = \"0\"\n",
    "                else:\n",
    "                    b[i] = str(int(n) - 1)\n",
    "            c = \"\".join(b)\n",
    "            lst2.add(c)\n",
    "\n",
    "        if target in lst2:\n",
    "            lst2.remove(target)\n",
    "\n",
    "        min_flag = False\n",
    "        for i in lst2:\n",
    "            if i not in deadends:\n",
    "                min_flag = True\n",
    "                break\n",
    "\n",
    "        return num if min_flag else num + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.target = int(target)\n",
    "        self.dead = list(map(int,deadends))\n",
    "        self.step = 0\n",
    "        self.list = [0 for _ in range(10000)]\n",
    "        for i in self.dead:\n",
    "            self.list[i] = 1\n",
    "        if self.list[0] == 1:\n",
    "            return -1\n",
    "        self.result = deque([\"0000\"])\n",
    "        while self.result:\n",
    "            num = len(self.result)\n",
    "            if self.list[self.target] == 1:\n",
    "                return self.step\n",
    "            for i in range(num):\n",
    "                list1 = list(self.result[i])\n",
    "                change1 = (int(list1[0]) - 1) % 10\n",
    "                list1[0] = str(change1)\n",
    "                node = \"\".join(list1)\n",
    "                if self.list[int(node)] == 0:\n",
    "                    self.result.append(node)\n",
    "                    self.list[int(node)] = 1\n",
    "\n",
    "                list2 = list(self.result[i])\n",
    "                change2 = (int(list2[0]) + 1) % 10\n",
    "                list2[0] = str(change2)\n",
    "                node = \"\".join(list2)\n",
    "                if self.list[int(node)] == 0:\n",
    "                    self.result.append(node)\n",
    "                    self.list[int(node)] = 1\n",
    "\n",
    "                list3 = list(self.result[i])\n",
    "                change3 = (int(list3[1]) - 1) % 10\n",
    "                list3[1] = str(change3)\n",
    "                node = \"\".join(list3)\n",
    "                if self.list[int(node)] == 0:\n",
    "                    self.result.append(node)\n",
    "                    self.list[int(node)] = 1\n",
    "\n",
    "                list4 = list(self.result[i])\n",
    "                change4 = (int(list4[1]) + 1) % 10\n",
    "                list4[1] = str(change4)\n",
    "                node = \"\".join(list4)\n",
    "                if self.list[int(node)] == 0:\n",
    "                    self.result.append(node)\n",
    "                    self.list[int(node)] = 1\n",
    "\n",
    "                list5 = list(self.result[i])\n",
    "                change5 = (int(list5[2]) - 1) % 10\n",
    "                list5[2] = str(change5)\n",
    "                node = \"\".join(list5)\n",
    "                if self.list[int(node)] == 0:\n",
    "                    self.result.append(node)\n",
    "                    self.list[int(node)] = 1\n",
    "\n",
    "                list6 = list(self.result[i])\n",
    "                change6 = (int(list6[2]) + 1) % 10\n",
    "                list6[2] = str(change6)\n",
    "                node = \"\".join(list6)\n",
    "                if self.list[int(node)] == 0:\n",
    "                    self.result.append(node)\n",
    "                    self.list[int(node)] = 1\n",
    "\n",
    "                list7 = list(self.result[i])\n",
    "                change7 = (int(list7[3]) - 1) % 10\n",
    "                list7[3] = str(change7)\n",
    "                node = \"\".join(list7)\n",
    "                if self.list[int(node)] == 0:\n",
    "                    self.result.append(node)\n",
    "                    self.list[int(node)] = 1\n",
    "\n",
    "                list8 = list(self.result[i])\n",
    "                change8 = (int(list8[3]) + 1) % 10\n",
    "                list8[3] = str(change8)\n",
    "                node = \"\".join(list8)\n",
    "                if self.list[int(node)] == 0:\n",
    "                    self.result.append(node)\n",
    "                    self.list[int(node)] = 1\n",
    "                self.list[int(self.result[i])] = 1\n",
    "            for i in range(num):\n",
    "                self.result.popleft()\n",
    "            self.step += 1\n",
    "        return -1\n",
    "\n",
    "# obj = Solution()\n",
    "# objlist = [\"0201\",\"0101\",\"0102\",\"1212\",\"2002\"]\n",
    "# objtar = \"0202\"\n",
    "# obj.openLock(objlist, objtar)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        双向BFS\n",
    "        url: https://leetcode-cn.com/explore/learn/card/queue-stack/217/queue-and-bfs/873/\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        deadends = set(deadends)\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        \n",
    "        set1 = set([\"0000\"])\n",
    "        set2 = set([target])\n",
    "        visited_set = set([\"0000\"])\n",
    "        step = 0\n",
    "\n",
    "        while set1 and set2:\n",
    "            if (len(set1) > len(set2)):\n",
    "                tmp = set1\n",
    "                set1 = set2\n",
    "                set2= tmp\n",
    "            tmp_set = set()\n",
    "            step += 1\n",
    "            for lock in set1:\n",
    "                for i in range(len(lock)):\n",
    "                    for t in [-1, 1]:\n",
    "                        next_lock = list(lock)\n",
    "                        next_lock[i] = str((int(lock[i]) + t) % 10)\n",
    "                        next_lock = \"\".join(next_lock)\n",
    "                        if next_lock in set2:\n",
    "                            return step\n",
    "                        if next_lock not in deadends and next_lock not in visited_set:\n",
    "                            tmp_set.add(next_lock)\n",
    "                            visited_set.add(next_lock)\n",
    "            set1 = tmp_set\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        target = int(target)\n",
    "        deadends = list(map(int, deadends))\n",
    "        queue = [(0,0)]\n",
    "        if 0 in deadends: return -1\n",
    "        compact = 32\n",
    "        bit_set = [0] * 10000\n",
    "        bit_set[0] = 1\n",
    "        for s in deadends: bit_set[s] = 1\n",
    "        # deadends.add(0)\n",
    "        i = 0\n",
    "        while i < len(queue):\n",
    "            state, step = queue[i]\n",
    "            i += 1\n",
    "            for j in range(4):\n",
    "                val = state // (10**j) % 10\n",
    "                state1 = state - val * 10**j\n",
    "                kval = [(val+9)%10, (val+1)%10]\n",
    "                for next_val in kval:\n",
    "                    new_state = state1 + 10**j * next_val\n",
    "                    if bit_set[new_state] == 0:#new_state not in deadends:\n",
    "                        if new_state == target:\n",
    "                            return step+1\n",
    "                        #deadends.add(new_state)\n",
    "                        bit_set[new_state] = 1\n",
    "                        queue.append((new_state, step+1))\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode-cn.com/problems/open-the-lock/\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        black = set(deadends)\n",
    "        visited = set()\n",
    "\n",
    "        def get_str_key(nums):\n",
    "            return ''.join([str((val + 10) % 10) for val in nums])\n",
    "\n",
    "        def check_match(node):\n",
    "            return get_str_key(node) == target\n",
    "\n",
    "        if '0000' in black:\n",
    "            return -1\n",
    "\n",
    "        orig = (0, 0, 0, 0)\n",
    "        target_val = [int(char) for char in target]\n",
    "\n",
    "        nodes = [orig]\n",
    "        visited.add(orig)\n",
    "        steps = 0\n",
    "        while nodes:\n",
    "\n",
    "            items = []\n",
    "            for node in nodes:\n",
    "\n",
    "                if check_match(node):\n",
    "                    return steps\n",
    "\n",
    "                for i in range(4):\n",
    "                    for factor in (1, -1):\n",
    "                        node1 = list(node)\n",
    "                        node1[i] += factor\n",
    "                        node1 = tuple(node1)\n",
    "                        if target_val[i] >= node1[i] >= target_val[i] - 10 \\\n",
    "                                and get_str_key(node1) not in black \\\n",
    "                                and node1 not in visited:\n",
    "                            items.append(node1)\n",
    "                            visited.add(node1)\n",
    "\n",
    "            nodes = items\n",
    "            steps += 1\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        from collections import deque\n",
    "        step = 0\n",
    "        v_search_queue = deque()\n",
    "        v_search_queue.append((step, '0000'))\n",
    "        v_visited = set(deadends)\n",
    "        \n",
    "        while v_search_queue:\n",
    "            temp = v_search_queue.popleft()\n",
    "            step_now = temp[0]\n",
    "            vertical_now = temp[1]\n",
    "\n",
    "            if vertical_now not in v_visited:\n",
    "                if vertical_now == target:\n",
    "                    return step_now\n",
    "                v_visited.add(vertical_now)\n",
    "                out = self.get_no_visited_neighbors(vertical_now, v_visited)\n",
    "                if out:\n",
    "                    out_new = [(step_now + 1, x) for x in out]\n",
    "                    v_search_queue.extend(out_new)\n",
    "\n",
    "        return -1\n",
    "    \n",
    "    def get_no_visited_neighbors(self, this_num, visited_list):\n",
    "\n",
    "        out = list()\n",
    "        for i, each in enumerate(this_num):\n",
    "            each_new = (int(each) + 1) % 10\n",
    "            each_new = str(each_new)\n",
    "            str_new = this_num[:i] + each_new + this_num[i + 1:]\n",
    "            if str_new not in visited_list:\n",
    "                out.append(str_new)\n",
    "            each_new = (int(each) - 1) % 10\n",
    "            each_new = str(each_new)\n",
    "            str_new = this_num[:i] + each_new + this_num[i + 1:]\n",
    "            if str_new not in visited_list:\n",
    "                out.append(str_new)\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        step = 0\n",
    "        wait = []\n",
    "        visited = set() #用元组可以确保不重复\n",
    "\n",
    "        cur = \"0000\"\n",
    "        if cur in deadends:\n",
    "            return -1\n",
    "        if cur == target:\n",
    "            return 0\n",
    "        wait.append((cur, step))\n",
    "\n",
    "\n",
    "        while wait != []:\n",
    "            (cur, step) = wait.pop(0)\n",
    "            for i in range(4):\n",
    "                trans = list(cur)\n",
    "                num = cur[i] #此时num是字符串\n",
    "\n",
    "                if num != '0' and num != '9':\n",
    "                    trans[i] = str(int(num) + 1)\n",
    "                    new = \"\".join(trans)\n",
    "                    if new == target:\n",
    "                        return step + 1\n",
    "                    if new not in deadends and new not in visited:\n",
    "                        wait.append((new, step + 1))\n",
    "                        visited.add(new) #确保不会对相同的字符串进行遍历\n",
    "\n",
    "                    trans[i] = str(int(num) - 1)\n",
    "                    new = \"\".join(trans)\n",
    "                    if new == target:\n",
    "                        return step + 1\n",
    "                    if new not in deadends and new not in visited:\n",
    "                        wait.append((new, step + 1))\n",
    "                        visited.add(new)\n",
    "\n",
    "                elif num == '0':\n",
    "                    trans[i] = '1'\n",
    "                    new = \"\".join(trans)\n",
    "                    if new == target:\n",
    "                        return step + 1\n",
    "                    if new not in deadends and new not in visited:\n",
    "                        wait.append((new, step + 1))\n",
    "                        visited.add(new)\n",
    "\n",
    "                    trans[i] = '9'\n",
    "                    new = \"\".join(trans)\n",
    "                    if new == target:\n",
    "                        return step + 1\n",
    "                    if new not in deadends and new not in visited:\n",
    "                        wait.append((new, step + 1))\n",
    "                        visited.add(new)\n",
    "\n",
    "                elif num == '9':\n",
    "                    trans[i] = '0'\n",
    "                    new = \"\".join(trans)\n",
    "                    if new == target:\n",
    "                        return step + 1\n",
    "                    if new not in deadends and new not in visited:\n",
    "                        wait.append((new, step + 1))\n",
    "                        visited.add(new)\n",
    "\n",
    "                    trans[i] = '8'\n",
    "                    new = \"\".join(trans)\n",
    "                    if new == target:\n",
    "                        return step + 1\n",
    "                    if new not in deadends and new not in visited:\n",
    "                        wait.append((new, step + 1))\n",
    "                        visited.add(new)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        deadends = set(deadends)\n",
    "\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        step = 0\n",
    "        used = set('0000')\n",
    "        stack = [('0000',step)]\n",
    "        while stack:\n",
    "            cur, step = stack.pop(0)\n",
    "            for j in range(4):\n",
    "                for i in [-1,1]:\n",
    "                    n = cur[:j]+chr((ord(cur[j]) - ord('0') + i + 10) % 10 + ord('0'))+cur[j+1:]\n",
    "                    if n == target:\n",
    "                        return step+1\n",
    "\n",
    "                    if n not in deadends and n not in used:\n",
    "                        stack.append([n,step+1])\n",
    "                        used.add(n)\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "# obj = Solution()\n",
    "# objlist = [\"0201\",\"0101\",\"0102\",\"1212\",\"2002\"]\n",
    "# objtar = \"0202\"\n",
    "# obj.openLock(objlist, objtar)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        begin = [\"0000\", 0]\n",
    "        search = collections.deque()\n",
    "        dead_set = set(deadends)\n",
    "        used = set()\n",
    "\n",
    "        if begin[0] not in dead_set:\n",
    "            search.append(begin)\n",
    "            used.add(begin[0])\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "        while search:\n",
    "            seed = search.popleft()\n",
    "            code = seed[0]\n",
    "            step = seed[1]\n",
    "\n",
    "            step += 1\n",
    "            for i in range(4):\n",
    "                new_code = code[0:i] + str((int(code[i]) + 1) % 10) + code[i + 1:]\n",
    "\n",
    "                if new_code not in dead_set and new_code not in used and new_code != target:\n",
    "                    search.append([new_code, step])\n",
    "                    used.add(new_code)\n",
    "                elif new_code == target:\n",
    "                    return step\n",
    "\n",
    "                new_code = code[0:i] + str((int(code[i]) - 1) % 10) + code[i + 1:]\n",
    "                if new_code not in dead_set and new_code not in used and new_code != target:\n",
    "                    search.append([new_code, step])\n",
    "                    used.add(new_code)\n",
    "                elif new_code == target:\n",
    "                    return step\n",
    "\n",
    "        return -1        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        import sys\n",
    "        deadends = set(deadends)\n",
    "        visited = set()\n",
    "        from collections import deque\n",
    "        q = deque()\n",
    "        start = ('0000', 0)\n",
    "        if start[0] in deadends:\n",
    "            return -1\n",
    "        visited.add(start[0])\n",
    "        q.appendleft(start)\n",
    "        min_length = 100000000\n",
    "        def add(s, n):\n",
    "            a = int(s) + n\n",
    "            if a < 0:\n",
    "                return '9'\n",
    "            elif a > 9:\n",
    "                return '0'\n",
    "            else:\n",
    "                return str(a)\n",
    "\n",
    "        while len(q) != 0:\n",
    "            tmp = q.popleft()\n",
    "            if tmp[0] == target and tmp[1] < min_length:\n",
    "                min_length = tmp[1]\n",
    "            if tmp[1] < min_length:\n",
    "                for i in range(4):\n",
    "                    up = tmp[0][0:i] + add(tmp[0][i], 1) + tmp[0][i + 1:]\n",
    "                    down = tmp[0][0:i] + add(tmp[0][i], -1) + tmp[0][i + 1:]\n",
    "                    if not (up in visited or up in deadends):\n",
    "                        q.append((up, tmp[1] + 1))\n",
    "                        visited.add(up)\n",
    "                    if not (down in visited or down in deadends):\n",
    "                        q.append((down, tmp[1] + 1))\n",
    "                        visited.add(down)\n",
    "        return -1 if min_length == 100000000 else min_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        moved, q, cnt, move = set(deadends), [\"0000\"], 0, {str(i): [str((i + 1) % 10), str((i - 1) % 10)] for i in range(10)}\n",
    "        if \"0000\" in moved:\n",
    "            return -1\n",
    "        while q:\n",
    "            new = []\n",
    "            cnt += 1\n",
    "            for s in q:\n",
    "                #s='0000'\n",
    "                for i, c in enumerate(s):\n",
    "                    # 0 0\n",
    "                    # 1 0\n",
    "                    # 2 0\n",
    "                    # 3 0\n",
    "                    for cur in (s[:i] + move[c][0] + s[i + 1:], s[:i] + move[c][1] + s[i + 1:]):#每次只能转动一个数字\n",
    "                        if cur not in moved:\n",
    "                            if cur == target:\n",
    "                                return cnt\n",
    "                            new.append(cur)\n",
    "                            moved.add(cur)\n",
    "            q = new\n",
    "        return -1\n",
    "                \n",
    "                \n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        movie,step,visit = set(deadends),0,collections.deque([(\"0000\",0)])\n",
    "        while visit:\n",
    "            string,step = visit.popleft()\n",
    "            if string==target:\n",
    "                return step\n",
    "            if string in movie:\n",
    "                continue\n",
    "            for i in range(4):\n",
    "                for x in [-1,1]:\n",
    "                    new_target = string[:i]+str((int(string[i])+x)%10)+string[i+1:]\n",
    "                    if new_target not in movie:\n",
    "                        visit.append([new_target,step+1])\n",
    "                        movie.add(string)\n",
    "        return -1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        deadset = set(deadends)\n",
    "        if(target in deadends) or (\"0000\" in deadends):\n",
    "            return -1\n",
    "        que = collections.deque()\n",
    "        que.append(\"0000\")\n",
    "        visited = set([\"0000\"])\n",
    "        step = 0\n",
    "        while que:\n",
    "            step += 1\n",
    "            size = len(que)\n",
    "            for i in range(size):\n",
    "                point = que.popleft()\n",
    "                for j in range(4):\n",
    "                    for k in range(-1, 2, 2):\n",
    "                        newPoint = [i for i in point]\n",
    "                        newPoint[j] = chr((ord(newPoint[j]) - ord('0') + k + 10)%10 + ord('0'))\n",
    "                        newPoint = \"\".join(newPoint)\n",
    "                        if newPoint == target:\n",
    "                            return step\n",
    "                        if (newPoint in deadset) or (newPoint in visited):\n",
    "                            continue\n",
    "                        que.append(newPoint)\n",
    "                        visited.add(newPoint)\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        if '0000' == target:\n",
    "            return 0\n",
    "            \n",
    "        deadends = set([tuple(i) for i in deadends])\n",
    "        target = tuple(target)\n",
    "\n",
    "        def move(r):\n",
    "            n = int(r)\n",
    "            a = n - 1 if n != 0 else 9\n",
    "            b = n + 1 if n != 9 else 0\n",
    "            return set([str(a), str(b)])\n",
    "\n",
    "        def find_one(cur):\n",
    "            res = set()\n",
    "            for i in range(4):\n",
    "                r = cur[i]\n",
    "                for n in move(r):\n",
    "                    s = cur[:i] + tuple(str(n)) + cur[i+1:]\n",
    "                    res.add(s)\n",
    "            return res            \n",
    "\n",
    "        def find_all(currunt):\n",
    "            res = set()\n",
    "            for cur in currunt:\n",
    "                res = res | find_one(cur)\n",
    "            return res\n",
    "\n",
    "        visited = set()\n",
    "        currunt = set()\n",
    "        currunt.add(tuple('0000'))\n",
    "        count = 0\n",
    "        while True:\n",
    "            count += 1\n",
    "            visited = visited | currunt\n",
    "            currunt = find_all(currunt) - deadends - visited\n",
    "            if not currunt:\n",
    "                return -1\n",
    "            if target in currunt:\n",
    "                return count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        # 定义一个距离函数，计算一个code直接拨需要多少下，比如0003就是3下，0099就是2下。\n",
    "        def dist(code):\n",
    "            return sum([min(int(c), 10 - int(c)) for c in code])\n",
    "\n",
    "        if \"0000\" in deadends or target in deadends:\n",
    "            return -1\n",
    "\n",
    "        # 由target反推能够到达target的所有前一个节点，放在 new_codes 里返回。\n",
    "        new_codes = []\n",
    "        for i in range(4):\n",
    "            pre, x, sur = target[:i], int(target[i]), target[i + 1:]\n",
    "            new_codes.append(pre + str((x + 1) % 10) + sur)\n",
    "            new_codes.append(pre + str((x - 1) % 10) + sur)\n",
    "\n",
    "\n",
    "        moves = set(new_codes) - set(deadends)\n",
    "        if not moves:\n",
    "            return -1\n",
    "\n",
    "        result = dist(target)  \n",
    "        for move in moves:\n",
    "            if dist(move) < result:  \n",
    "                return result  \n",
    "        return result + 2  \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        # 定义一个距离函数，计算一个code直接拨需要多少下，比如0003就是3下，0099就是2下。\n",
    "        def dist(code):\n",
    "            return sum([min(int(c), 10-int(c)) for c in code])\n",
    "        \n",
    "        if \"0000\" in deadends or target in deadends :\n",
    "            return -1\n",
    "\n",
    "        # 由target反推能够到达target的所有前一个节点，放在 new_codes 里返回。\n",
    "        new_codes = []\n",
    "        for i in range(4):\n",
    "            pre, x, sur = target[:i], int(target[i]), target[i+1:]\n",
    "            new_codes.append(pre + str((x+1)%10) + sur)\n",
    "            new_codes.append(pre + str((x-1)%10) + sur)\n",
    "        \n",
    "        # 利用集合（set）是可以做减法，得出不在deadends里面的new_codes，放在 moves 里。\n",
    "        # set的减法：例如{'0001','0005','0016'} - {'0005','0007'} = {'0001', '0016'}\n",
    "        moves = set(new_codes) - set(deadends)\n",
    "        # 如果moves为空，那就说明没有路径可以到达target，那就返回 -1\n",
    "        if not moves:\n",
    "            return -1\n",
    "        \n",
    "        result = dist(target)  # 例如 result = dist('0888') ，那么 result就等于6，代表到达target的理论最短路径长度\n",
    "        for move in moves:\n",
    "            if dist(move) < result: # <------\n",
    "                return result       # <------ dist(move)比result小时，说明存在最短路径，即可返回理论最短\n",
    "        return result + 2           # <------ 不存在理论最短路径时，需要将8个相邻结点中的可达结点中差别位先调成功（从较近的那侧），然后将其他位调到target中的相应数字，再将那一位调回来，比理论最短路径长度+2。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        visited = [False]*(10**4)\n",
    "        nos = [False]*(10**4)\n",
    "        for x in deadends:\n",
    "            nos[int(x)]=True\n",
    "        que = deque()\n",
    "        count = 0\n",
    "        start = \"0000\"\n",
    "        if nos[int(start)]:\n",
    "            return -1\n",
    "        que.append(start)\n",
    "        visited[int(start)] = True\n",
    "        def next_digit(digit,forward=True):\n",
    "            if forward:\n",
    "                return (0 if digit==9 else digit+1)\n",
    "            else:\n",
    "                return (9 if digit==0 else digit-1)\n",
    "            \n",
    "        while que:\n",
    "            cur_len = len(que)\n",
    "            count+=1\n",
    "            for _ in range(cur_len):\n",
    "                cur = que.popleft()\n",
    "                for x in range(4):\n",
    "                    for y in (True,False):\n",
    "                        cur_cop = list(cur)\n",
    "                        cur_cop[x] = str(next_digit(int(cur[x]),y))\n",
    "                        cur_next = \"\".join(cur_cop)\n",
    "                        if not visited[int(cur_next)] and not nos[int(cur_next)]:\n",
    "                            que.append(cur_next)\n",
    "                            visited[int(cur_next)]=True\n",
    "                            if target==cur_next:\n",
    "                                return count\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "\n",
    "        # # 定义一个距离函数，计算一个code直接拨需要多少下，比如0003就是3下，0099就是2下。\n",
    "        # def dist(code):\n",
    "        #     return sum([min(int(c), 10-int(c)) for c in code])\n",
    "        \n",
    "        # if \"0000\" in deadends or target in deadends :\n",
    "        #     return -1\n",
    "\n",
    "        # # 由target反推能够到达target的所有前一个节点，放在 new_codes 里返回。\n",
    "        # new_codes = []\n",
    "        # for i in range(4):\n",
    "        #     pre, x, sur = target[:i], int(target[i]), target[i+1:]\n",
    "        #     new_codes.append(pre + str((x+1)%10) + sur)\n",
    "        #     new_codes.append(pre + str((x-1)%10) + sur)\n",
    "        \n",
    "        # # 利用集合（set）是可以做减法，得出不在deadends里面的new_codes，放在 moves 里。\n",
    "        # # set的减法：例如{'0001','0005','0016'} - {'0005','0007'} = {'0001', '0016'}\n",
    "        # moves = set(new_codes) - set(deadends)\n",
    "        # # 如果moves为空，那就说明没有路径可以到达target，那就返回 -1\n",
    "        # if not moves:\n",
    "        #     return -1\n",
    "        \n",
    "        # result = dist(target)  # 例如 result = dist('0888') ，那么 result就等于6\n",
    "        # # 接下来我就不太明白了....\n",
    "        # for move in moves:\n",
    "        #     if dist(move) < result: # <------\n",
    "        #         return result       # <------ 尤其这三行，为啥dist(move)比result小时，就返回result\n",
    "        # return result + 2           # <------ 否则就返回 result + 2 ，为啥+2 ？ \n",
    "\n",
    "        def distance(string):\n",
    "            return sum(min(int(num), 10 - int(num)) for num in string)        \n",
    "\n",
    "        if '0000' in deadends or target in deadends:\n",
    "            return -1\n",
    "\n",
    "        moves = {str(i): (str((i - 1) % 10), str((i + 1) % 10)) for i in range(10)}\n",
    "        adjacent = set()\n",
    "\n",
    "        for i in range(len(target)):\n",
    "            start = target[:i]\n",
    "            end = target[i + 1:]\n",
    "            for j in moves[target[i]]:\n",
    "                adjacent.add(start + j + end)\n",
    "\n",
    "        possibleMoves = adjacent - set(deadends)\n",
    "\n",
    "        if not possibleMoves:\n",
    "            return -1\n",
    "\n",
    "        return min(distance(move) for move in possibleMoves) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == '0000': return 0\n",
    "        if '0000' in deadends: return -1\n",
    "        dead = set(deadends)\n",
    "        start, end = {'0000'}, {target}\n",
    "        count = 0\n",
    "        visited = {'0000'}\n",
    "        while start and end:\n",
    "            count += 1\n",
    "            tmp = set()\n",
    "            if len(start) > len(end):\n",
    "                start, end = end, start\n",
    "            for s in start:\n",
    "                for i in range(4):\n",
    "                    for d in [-1, 1]:\n",
    "                        cur = s[:i] + str((int(s[i]) + d) % 10) + s[i + 1:]\n",
    "                        if cur in end: return count\n",
    "                        if cur not in dead and cur not in visited:\n",
    "                            tmp.add(cur)\n",
    "                            visited.add(cur)\n",
    "\n",
    "            start = tmp\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        tmp_list_1 = []\n",
    "        if '0000' == target:\n",
    "            return 0\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        if target in deadends:\n",
    "            return -1\n",
    "        tmp_list_1.append('0000')\n",
    "        tmp_list_2 = []\n",
    "        tmp_list_2.append(target)\n",
    "        depth = 1\n",
    "        deadends.append('0000')\n",
    "        while tmp_list_1:\n",
    "            new_tmp_list = []\n",
    "            for i in tmp_list_1:\n",
    "                for tmp_ind in range(4):\n",
    "                    new_num_1 = i[:tmp_ind] + str((int(i[tmp_ind])+1)%10) + i[tmp_ind+1:]\n",
    "                    new_num_2 = i[:tmp_ind] + str((int(i[tmp_ind])-1)%10) + i[tmp_ind+1:]\n",
    "                    if (new_num_1 in tmp_list_2) or (new_num_2 in tmp_list_2):\n",
    "                        return depth\n",
    "                    if new_num_1 not in deadends:\n",
    "                        new_tmp_list.append(new_num_1)\n",
    "                        deadends.append(new_num_1)\n",
    "                    if new_num_2 not in deadends:\n",
    "                        new_tmp_list.append(new_num_2)\n",
    "                        deadends.append(new_num_2)\n",
    "            tmp_list_1 = tmp_list_2\n",
    "            tmp_list_2 = new_tmp_list\n",
    "            depth += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target: str) -> int:\n",
    "\n",
    "        q1 = set()\n",
    "        q1.add('0000')\n",
    "        q2 = set()\n",
    "        q2.add(target)\n",
    "        cnt = 0\n",
    "        visited = set()\n",
    "\n",
    "        while len(q1) > 0 and len(q2) > 0:\n",
    "\n",
    "            temp_adjs = set()\n",
    "            for temp_pwd in q1:\n",
    "                if temp_pwd in deadends:\n",
    "                    continue\n",
    "\n",
    "                if temp_pwd in q2:\n",
    "                    return cnt\n",
    "\n",
    "                visited.add(temp_pwd)\n",
    "\n",
    "                for pos in range(4):\n",
    "                    minus_one = self.minusOne(temp_pwd, pos)\n",
    "                    plus_one = self.plusOne(temp_pwd, pos)\n",
    "\n",
    "                    if minus_one not in visited:\n",
    "                        temp_adjs.add(minus_one)\n",
    "\n",
    "                    if plus_one not in visited:\n",
    "                        temp_adjs.add(plus_one)\n",
    "\n",
    "            q1 = q2\n",
    "            q2 = temp_adjs\n",
    "            cnt += 1\n",
    "\n",
    "        return -1\n",
    "\n",
    "    def minusOne(self, pwd, pos):\n",
    "        new_pwd = list(pwd)\n",
    "        if new_pwd[pos] == '0':\n",
    "            new_pwd[pos] = '9'\n",
    "        else:\n",
    "            new_pwd[pos] = str(int(new_pwd[pos]) - 1)\n",
    "        return ''.join(new_pwd)\n",
    "\n",
    "    def plusOne(self, pwd, pos):\n",
    "        new_pwd = list(pwd)\n",
    "        if new_pwd[pos] == '9':\n",
    "            new_pwd[pos] = '0'\n",
    "        else:\n",
    "            new_pwd[pos] = str(int(new_pwd[pos]) + 1)\n",
    "        return ''.join(new_pwd)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def add_num(self, num):\n",
    "        if num == '9':\n",
    "            return '0'\n",
    "        else:\n",
    "            return str(int(num) + 1)\n",
    "\n",
    "    def min_num(self, num):\n",
    "        if num == '0':\n",
    "            return '9'\n",
    "        else:\n",
    "            return str(int(num) - 1)\n",
    "\n",
    "    def next_adj(self, cur):\n",
    "        for i, num in enumerate(cur):\n",
    "            yield cur[:i] + self.min_num(num) + cur[i + 1:]\n",
    "            yield cur[:i] + self.add_num(num) + cur[i + 1:]\n",
    "\n",
    "\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        deadends_set = set(deadends)\n",
    "\n",
    "        init_security = ['0000']\n",
    "        queue = deque(init_security)\n",
    "        visited = set(init_security)\n",
    "        step = 0\n",
    "\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                cur = queue.popleft()\n",
    "                if cur == target:\n",
    "                    return step\n",
    "                # 跳过死路\n",
    "                if cur in deadends_set:\n",
    "                    continue\n",
    "                for i in self.next_adj(cur):\n",
    "                    if not i in visited:\n",
    "                        queue.append(i)\n",
    "                        visited.add(i)\n",
    "            step += 1\n",
    "        else:\n",
    "            return -1\n",
    "    \n",
    "    # 双向bfs\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        deadends_set = set(deadends)\n",
    "\n",
    "        q1 = set(['0000'])\n",
    "        q2 = set([target])\n",
    "        visited = set([])\n",
    "\n",
    "        step = 0\n",
    "\n",
    "        while q1 and q2:\n",
    "            if len(q1) > len(q2):\n",
    "                q1, q2 = q2, q1\n",
    "            temp = set([]) \n",
    "            for cur in q1:\n",
    "                if cur in deadends_set:\n",
    "                    continue\n",
    "                if cur in q2:\n",
    "                    return step\n",
    "                visited.add(cur)\n",
    "                for i in self.next_adj(cur):\n",
    "                    if not i in visited:\n",
    "                        temp.add(i)\n",
    "            step += 1\n",
    "            q1 = q2\n",
    "            q2 = temp\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        dire = []\n",
    "        for i in range(4):\n",
    "            dire.append(target[:i]+str((int(target[i])+1)%10)+target[i+1:])\n",
    "            dire.append(target[:i]+str((int(target[i])+9)%10)+target[i+1:])\n",
    "        if sorted(dire)==sorted(deadends) or \"0000\" in deadends:\n",
    "            return -1\n",
    "        q = queue.Queue()\n",
    "        visited = set(deadends)\n",
    "  \n",
    "        q.put(\"0000\")\n",
    "        visited.add(\"0000\")\n",
    "        step = 0\n",
    "        while not q.empty():\n",
    "            n = q.qsize()\n",
    "            for i in range(n):\n",
    "                x = q.get()\n",
    "               \n",
    "                if x==target:\n",
    "                    return step\n",
    "                \n",
    "                dire = []\n",
    "                for i in range(4):\n",
    "                    dire.append(x[:i]+str((int(x[i])+1)%10)+x[i+1:])\n",
    "                    dire.append(x[:i]+str((int(x[i])+9)%10)+x[i+1:])\n",
    "\n",
    "                for d in dire:\n",
    "                    if d not in visited:\n",
    "                        visited.add(d)\n",
    "                        q.put(d)\n",
    "            step += 1\n",
    "        return -1\n",
    "\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        def plus_one(s: str, j: int):\n",
    "            if s[j] == '9':\n",
    "                s = s[0:j] + '0' + s[j+1:]\n",
    "            else:\n",
    "                s = s[0:j] + str(int(s[j]) + 1) + s[j + 1:]\n",
    "            return s\n",
    "\n",
    "        def minus_one(s: str, j: int):\n",
    "            if s[j] == '0':\n",
    "                s = s[0:j] + '9' + s[j+1:]\n",
    "            else:\n",
    "                s = s[0:j] + str(int(s[j]) - 1) + s[j + 1:]\n",
    "            return s\n",
    "        \n",
    "        q = ['0000']\n",
    "        visited = set()\n",
    "        visited.add('0000')  \n",
    "        deadends = list(deadends)\n",
    "        step = 0\n",
    "        while q:\n",
    "            for i in range(len(q)):\n",
    "                cur = q.pop(0)\n",
    "                \n",
    "                # 判断是否到达终点\n",
    "                if cur in deadends:\n",
    "                    continue\n",
    "                if cur == target:\n",
    "                    return step\n",
    "                \n",
    "                for j in range(4):\n",
    "                    up = plus_one(cur, j)\n",
    "                    if up not in visited:\n",
    "                        q.append(up)\n",
    "                        visited.add(up)\n",
    "                    down = minus_one(cur, j)\n",
    "                    if down not in visited:\n",
    "                        q.append(down)\n",
    "                        visited.add(down)\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        dead = {x for x in deadends}\n",
    "        queue = [\"0000\"]\n",
    "        depth = 0\n",
    "        seen = {\"0000\"}\n",
    "\n",
    "        def neighbors(node):\n",
    "            for index in range(4):\n",
    "                x = int(node[index])\n",
    "                for next in (-1, 1):\n",
    "                    y = (x + next) % 10\n",
    "                    yield node[:index] + str(y) + node[index + 1:]\n",
    "\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                if node == target:\n",
    "                    return depth\n",
    "                if node in dead:\n",
    "                    continue\n",
    "                for nei in neighbors(node):\n",
    "                    if nei not in seen:\n",
    "                        seen.add(nei)\n",
    "                        queue.append(nei)\n",
    "            depth += 1\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if(\"0000\" in deadends):\n",
    "            return -1\n",
    "        used = [0] * 10000\n",
    "        used[0] = 1\n",
    "        queue = [\"0000\"]\n",
    "        depth = 0\n",
    "        while len(queue) >0:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                cur_num_str = queue.pop(0)\n",
    "                if(cur_num_str == target):\n",
    "                    return depth\n",
    "                for i in range(4):\n",
    "                    cur_str = cur_num_str[i]\n",
    "                    up_num = int(cur_str)+1\n",
    "                    up_str =  str(up_num%10)\n",
    "                    next_str1 = cur_num_str[:i] + up_str + cur_num_str[i+1:]\n",
    "                    if(next_str1 not in deadends and used[int(next_str1)] == 0):\n",
    "                        queue.append(next_str1)\n",
    "                        used[int(next_str1)] = 1\n",
    "                    down_num = int(cur_str) - 1\n",
    "                    if(down_num < 0):\n",
    "                        down_num = 9\n",
    "                    down_str =  str(down_num)\n",
    "                    next_str2 = cur_num_str[:i] + down_str + cur_num_str[i+1:]\n",
    "                    if(next_str2 not in deadends and used[int(next_str2)] == 0):\n",
    "                        queue.append(next_str2)\n",
    "                        used[int(next_str2)] = 1\n",
    "            depth+=1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visited = []\n",
    "        self.adjNumberMap = {str(n):self.adjNumber(str(n)) for n in range(10)}\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        self.visited.append(target)\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        start = target\n",
    "        target = \"0000\"\n",
    "        cost = 0\n",
    "        if start == target:\n",
    "            return cost\n",
    "        cost +=1\n",
    "        stack = []\n",
    "        for nextStat in self.getAdj(start):\n",
    "            if nextStat not in self.visited and nextStat not in deadends:\n",
    "                stack.append([nextStat,cost,self.getDist(nextStat,target)])\n",
    "                self.visited.append(nextStat)\n",
    "        stack = sorted(stack, key = lambda x :x[1]+2*x[2])\n",
    "        count = 0\n",
    "        while (stack):\n",
    "            count+=1\n",
    "            [stat, cost, dist] = stack.pop(0)\n",
    "            if stat == target:\n",
    "                return cost\n",
    "            cost +=1\n",
    "            for nextStat in self.getAdj(stat):\n",
    "                if nextStat not in self.visited and nextStat not in deadends:\n",
    "                    stack.append([nextStat,cost,self.getDist(nextStat,target)])\n",
    "                    self.visited.append(nextStat)\n",
    "            stack = sorted(stack, key = lambda x :x[1]+2*x[2])\n",
    "            if count > 100:\n",
    "                break\n",
    "        return -1\n",
    "\n",
    "\n",
    "    def getDist(self,start,end):\n",
    "        cStart = [c for c in start]\n",
    "        cEnd = [c for c in end]\n",
    "        dist = 0\n",
    "        for i in range(4):\n",
    "           small = min(cStart[i],cEnd[i])\n",
    "           large = max(cStart[i],cEnd[i])\n",
    "           dist += min(ord(large) - ord(small), ord(small) -ord(large) + 10)\n",
    "        return dist\n",
    "\n",
    "    def getAdj(self,start):\n",
    "        result = []\n",
    "        for i in range(4):\n",
    "            tempc = [c for c in start]\n",
    "            for n in self.adjNumber(tempc[i]):\n",
    "                tempc[i] = n\n",
    "                result.append(\"\".join(tempc))\n",
    "        return result\n",
    "    def adjNumber(self,character):\n",
    "        if character >=\"1\" and character <=\"8\":\n",
    "            return (chr(ord(character) -1), chr(ord(character) +1))\n",
    "        elif character == \"0\":\n",
    "            return (\"1\",\"9\")\n",
    "        elif character == \"9\":\n",
    "            return (\"8\",\"0\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_up(self, c):\n",
    "        return str(int(c)+1) if c != '9' else '0'\n",
    "    def get_down(self, c):\n",
    "        return str(int(c)-1) if c != '0' else '9'\n",
    "    def get_status(self, s):\n",
    "        s = list(s)\n",
    "        for i in range(4):\n",
    "            num = s[i]\n",
    "            s[i] = self.get_up(num)\n",
    "            yield ''.join(s)\n",
    "            s[i] = self.get_down(num)\n",
    "            yield ''.join(s)\n",
    "            s[i] = num\n",
    "    #普通广度优先遍历\n",
    "    def openLock_bfs(self, deadends: List[str], target: str) -> int:\n",
    "        deadends = set(deadends)\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        q = deque()\n",
    "        q.append(('0000', 1)) #记录当前状态和深度\n",
    "        visit = {'0000'}\n",
    "        while q:\n",
    "            st, step = q.popleft()\n",
    "            for next in self.get_status(st):\n",
    "                if next not in visit and next not in deadends:\n",
    "                    if next == target:\n",
    "                        return step\n",
    "                    q.append((next, step+1))\n",
    "                    visit.add(next)\n",
    "        return -1\n",
    "\n",
    "    def bfs(self, q, v1, v2, deadends):\n",
    "        for _ in range(len(q)):\n",
    "            st = q.popleft()\n",
    "            step = v1[st]\n",
    "            for next in self.get_status(st):\n",
    "                if next not in v1 and next not in deadends:\n",
    "                    if next in v2:\n",
    "                        return step + 1 + v2[next]\n",
    "                    else:\n",
    "                        v1[next] = step + 1\n",
    "                        q.append(next)\n",
    "        return -1\n",
    "\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        deadends = set(deadends)\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        q1, q2 = deque(), deque()\n",
    "        q1.append('0000')  # 记录当前状态和深度\n",
    "        q2.append(target)\n",
    "        v1, v2 = Counter(), Counter()\n",
    "        v1['0000'] = 0\n",
    "        v2[target] = 0\n",
    "        while q1 and q2:\n",
    "            #双向bfs，每次先遍历短的队列\n",
    "            if len(q1) <= len(q2):\n",
    "                step = self.bfs(q1, v1, v2, deadends)\n",
    "            else:\n",
    "                step = self.bfs(q2, v2, v1, deadends)\n",
    "            if step != -1:\n",
    "                return step\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_up(self, c):\n",
    "        return str(int(c)+1) if c != '9' else '0'\n",
    "    def get_down(self, c):\n",
    "        return str(int(c)-1) if c != '0' else '9'\n",
    "    def get_status(self, s):\n",
    "        s = list(s)\n",
    "        for i in range(4):\n",
    "            num = s[i]\n",
    "            s[i] = self.get_up(num)\n",
    "            yield ''.join(s)\n",
    "            s[i] = self.get_down(num)\n",
    "            yield ''.join(s)\n",
    "            s[i] = num\n",
    "    #普通广度优先遍历\n",
    "    def openLock_bfs(self, deadends: List[str], target: str) -> int:\n",
    "        deadends = set(deadends)\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        q = deque()\n",
    "        q.append(('0000', 1)) #记录当前状态和深度\n",
    "        visit = {'0000'}\n",
    "        while q:\n",
    "            st, step = q.popleft()\n",
    "            for next in self.get_status(st):\n",
    "                if next not in visit and next not in deadends:\n",
    "                    if next == target:\n",
    "                        return step\n",
    "                    q.append((next, step+1))\n",
    "                    visit.add(next)\n",
    "        return -1\n",
    "\n",
    "    def bfs(self, q, v1, v2, deadends):\n",
    "        for _ in range(len(q)):\n",
    "            st = q.popleft()\n",
    "            step = v1[st]\n",
    "            for next in self.get_status(st):\n",
    "                if next not in v1 and next not in deadends:\n",
    "                    if next in v2:\n",
    "                        return step + 1 + v2[next]\n",
    "                    else:\n",
    "                        v1[next] = step + 1\n",
    "                        q.append(next)\n",
    "        return -1\n",
    "\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        deadends = set(deadends)\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        q1, q2 = deque(), deque()\n",
    "        q1.append('0000')  # 记录当前状态和深度\n",
    "        q2.append(target)\n",
    "        v1, v2 = Counter(), Counter()\n",
    "        v1['0000'] = 0\n",
    "        v2[target] = 0\n",
    "        while q1 and q2:\n",
    "            #双向bfs，每次先遍历短的队列\n",
    "            if len(q1) <= len(q2):\n",
    "                step = self.bfs(q1, v1, v2, deadends)\n",
    "            else:\n",
    "                step = self.bfs(q2, v2, v1, deadends)\n",
    "            if step != -1:\n",
    "                return step\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        \"\"\"双向BFS\"\"\"\n",
    "        def up_shifts(s, i):\n",
    "            arr = list(s)\n",
    "            arr[i] = '9' if arr[i] == '0' else str(int(arr[i]) - 1)\n",
    "            return \"\".join(arr)\n",
    "        \n",
    "        def down_shifts(s, i):\n",
    "            arr = list(s)\n",
    "            arr[i] = '0' if arr[i] == '9' else str(int(arr[i]) + 1)\n",
    "            return \"\".join(arr)\n",
    "        \n",
    "        visited = {}\n",
    "        deadends = set(deadends)\n",
    "        q1, q2 = set(['0000']), set([target])\n",
    "        step = 0\n",
    "        while q1 and q2:\n",
    "            tmp = set([])\n",
    "            for cur in q1:\n",
    "                if cur in visited or cur in deadends:\n",
    "                    continue\n",
    "                visited[cur] = 1\n",
    "\n",
    "                for i in range(4):\n",
    "                    up = up_shifts(cur, i)\n",
    "                    tmp.add(up)\n",
    "                    \n",
    "                    down = down_shifts(cur, i)\n",
    "                    tmp.add(down)\n",
    "                \n",
    "                if cur in q2:\n",
    "                    return step\n",
    "            step += 1\n",
    "                \n",
    "            q1 = q2\n",
    "            q2 = tmp\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visited = []\n",
    "        self.adjNumberMap = {str(n):self.adjNumber(str(n)) for n in range(10)}\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        self.visited.append(target)\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        start = target\n",
    "        target = \"0000\"\n",
    "        cost = 0\n",
    "        if start == target:\n",
    "            return cost\n",
    "        cost +=1\n",
    "        stack = []\n",
    "        for nextStat in self.getAdj(start):\n",
    "            if nextStat not in self.visited and nextStat not in deadends:\n",
    "                stack.append([nextStat,cost,self.getDist(nextStat,target)])\n",
    "                self.visited.append(nextStat)\n",
    "        stack = sorted(stack, key = lambda x :x[1]+2*x[2])\n",
    "        count = 0\n",
    "        while (stack):\n",
    "            count+=1\n",
    "            [stat, cost, dist] = stack.pop(0)\n",
    "            if stat == target:\n",
    "                return cost\n",
    "            cost +=1\n",
    "            for nextStat in self.getAdj(stat):\n",
    "                if nextStat not in self.visited and nextStat not in deadends:\n",
    "                    stack.append([nextStat,cost,self.getDist(nextStat,target)])\n",
    "                    self.visited.append(nextStat)\n",
    "            stack = sorted(stack, key = lambda x :x[1]+2*x[2])\n",
    "            if count > 100:\n",
    "                break\n",
    "        return -1\n",
    "    def getDist(self,start,end):\n",
    "        cStart = [c for c in start]\n",
    "        cEnd = [c for c in end]\n",
    "        dist = 0\n",
    "        for i in range(4):\n",
    "           small = min(cStart[i],cEnd[i])\n",
    "           large = max(cStart[i],cEnd[i])\n",
    "           dist += min(ord(large) - ord(small), ord(small) -ord(large) + 10)\n",
    "        return dist\n",
    "\n",
    "    def getAdj(self,start):\n",
    "        result = []\n",
    "        for i in range(4):\n",
    "            tempc = [c for c in start]\n",
    "            for n in self.adjNumber(tempc[i]):\n",
    "                tempc[i] = n\n",
    "                result.append(\"\".join(tempc))\n",
    "        return result\n",
    "    def adjNumber(self,character):\n",
    "        if character >=\"1\" and character <=\"8\":\n",
    "            return (chr(ord(character) -1), chr(ord(character) +1))\n",
    "        elif character == \"0\":\n",
    "            return (\"1\",\"9\")\n",
    "        elif character == \"9\":\n",
    "            return (\"8\",\"0\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        # 双向BFS\n",
    "        leftQ = deque([\"0000\"])\n",
    "        rightQ = deque([target])\n",
    "        leftH = {\"0000\":0}\n",
    "        rightH = {target: 0}\n",
    "        res = -1\n",
    "        if \"0000\" == target:\n",
    "            return 0\n",
    "        if \"0000\" in deadends or target in deadends:\n",
    "            return res\n",
    "        def getNextNodes(node):\n",
    "            nextNodeList = []\n",
    "            nodeNums = [x for x in node]\n",
    "            for i in range(4):\n",
    "                curVal = int(nodeNums[i])\n",
    "                # + 1\n",
    "                upNode = nodeNums[::]\n",
    "                if curVal == 9:\n",
    "                    upNode[i] = '0'\n",
    "                else:\n",
    "                    upNode[i] = str(curVal + 1)\n",
    "                # -1\n",
    "                downNode = nodeNums[::]\n",
    "                if curVal == 0:\n",
    "                    downNode[i] = '9'\n",
    "                else:\n",
    "                    downNode[i] = str(curVal - 1)\n",
    "                nextNodeList.extend([\"\".join(upNode), \"\".join(downNode)])\n",
    "            return nextNodeList\n",
    "\n",
    "        def bfs(queue, curMemo, otherMemo):\n",
    "            curNode = queue.popleft()\n",
    "            step = curMemo[curNode] if curNode in curMemo else 0\n",
    "            nextNodeList = getNextNodes(curNode)\n",
    "            for nextNode in nextNodeList:\n",
    "                if nextNode not in curMemo and nextNode not in deadends:\n",
    "                    if nextNode in otherMemo:\n",
    "                        return step + otherMemo[nextNode] + 1\n",
    "\n",
    "                    curMemo[nextNode] = step + 1\n",
    "                    queue.append(nextNode)\n",
    "            return -1\n",
    "\n",
    "        while leftQ and rightQ:\n",
    "            if len(leftQ) < len(rightQ): # 每次最小队列去bfs，保证两边并行\n",
    "                res = bfs(leftQ, leftH, rightH)\n",
    "            else:\n",
    "                res = bfs(rightQ, rightH, leftH)\n",
    "            if res != -1:\n",
    "                return res\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        #进行双向BFS搜索，q1从起点开始,q2从目标开始\n",
    "        q1=set([0])\n",
    "        q2=set([int(target)]) #将目标转换为int形式\n",
    "        visit=set() #已经访问集合\n",
    "        for dead in deadends: #黑名单和已访问同性质，所以放入一个集合\n",
    "            visit.add(int(dead))\n",
    "        #如果起点已经在deadends中，直接返回-1\n",
    "        if 0 in visit:\n",
    "            return -1\n",
    "        #初始步数为0\n",
    "        step=0\n",
    "        while q1 and q2: #当q1,q2均不为空\n",
    "            #选择其中较小的来进行，减少空间使用，最坏情况是始终使用q1，变为普通BFS\n",
    "            if len(q1) > len(q2):\n",
    "                q1,q2 = q2,q1\n",
    "            #set无法在遍历中改变，所以new一个\n",
    "            newq1=set()\n",
    "            for number in q1: #当集合q1q2出现交集，说明出现了路径\n",
    "                if number in q2:\n",
    "                    return step\n",
    "                    #在循环外加入visit，以免无法出现交集\n",
    "                visit.add(number)\n",
    "                for i in [1,10,100,1000]:# 对个十百千位加减，所以取值1,10,100,1000\n",
    "                    #对10位加1就是对百位取整（//),然后对取余(%)剩下数字+10再取余\n",
    "                    #1292-> 1200，92+10=102->2\n",
    "                    newNumber=number//(i*10) * (i*10) + (number%(i*10)+i)%(i*10) #向上拨\n",
    "                    if newNumber not in visit:\n",
    "                        newq1.add(newNumber) #将转化完的数字放入新集合\n",
    "                    newNumber=number//(i*10) * (i*10) + (number%(i*10)-i)%(i*10) #向下拨\n",
    "                    if newNumber not in visit:\n",
    "                        newq1.add(newNumber)\n",
    "            #完成遍历，+1步\n",
    "            step += 1\n",
    "            #将newq1给q1继续\n",
    "            q1=newq1\n",
    "            #循环完成也无交集，说明没路径了\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == '0000':\n",
    "            return 0\n",
    "        m = len(target)\n",
    "        dead_set = set(deadends)\n",
    "        if '0000' in dead_set:\n",
    "            return -1\n",
    "        visited_s = set(['0000'])\n",
    "        visited_e = set([target])\n",
    "        q_s = ['0000']\n",
    "        q_e = [target]\n",
    "        count = 0\n",
    "        while q_s and q_e:\n",
    "            if len(q_s) > len(q_e):\n",
    "                visited_s, visited_e = visited_e, visited_s\n",
    "                q_s, q_e = q_e, q_s\n",
    "            for _ in range(len(q_s)):\n",
    "                cur = q_s.pop(0)\n",
    "                if cur in visited_e:\n",
    "                    return count\n",
    "                for i in range(m):\n",
    "                    for diff in (-1, 1):\n",
    "                        tmp = cur[:i] + str((int(cur[i]) + diff) % 10) + cur[i+1:]\n",
    "                        if tmp not in dead_set and tmp not in visited_s:\n",
    "                            q_s.append(tmp)\n",
    "                            visited_s.add(tmp)\n",
    "            count += 1\n",
    "        return -1\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == \"0000\":\n",
    "            return 0\n",
    "        def do_up(num):\n",
    "            return '0' if num == '9' else str(int(num) + 1)\n",
    "\n",
    "        def do_down(num):\n",
    "            return '9' if num == '0' else str(int(num) - 1)\n",
    "\n",
    "        mem = {}\n",
    "        for deadend in deadends:\n",
    "            mem[deadend] = 1\n",
    "            \n",
    "        if '0000' in mem:\n",
    "            return -1\n",
    "\n",
    "        stack = ['0000']\n",
    "        mem['0000'] = 1\n",
    "        level = 0\n",
    "\n",
    "        while stack:\n",
    "            this_level = []\n",
    "            for num_str in stack:\n",
    "                for index in range(4):\n",
    "                    up_num = do_up(num_str[index])\n",
    "                    down_num = do_down(num_str[index])\n",
    "\n",
    "                    up_str = num_str[:index] + up_num + num_str[index+1:]\n",
    "                    down_str = num_str[:index] + down_num + num_str[index+1:]\n",
    "\n",
    "                    if up_str == target or down_str == target:\n",
    "                        return level + 1\n",
    "                    if up_str not in mem:  \n",
    "                        mem[up_str] = 1\n",
    "                        this_level.append(up_str)\n",
    "                    if down_str not in mem:\n",
    "                        mem[down_str] = 1\n",
    "                        this_level.append(down_str)\n",
    "            if not this_level:\n",
    "                return -1\n",
    "            stack = this_level\n",
    "            level += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        def add_p(c):\n",
    "            if '0' <= c <= '8':\n",
    "                return chr(ord(c) + 1)\n",
    "            else:\n",
    "                return '0'\n",
    "\n",
    "        def plus_p(c):\n",
    "            if '1' <= c <= '9':\n",
    "                return chr(ord(c) - 1)\n",
    "            else:\n",
    "                return '9'\n",
    "\n",
    "        def lingju(cur):\n",
    "            for i in range(4):\n",
    "                yield cur[:i] + add_p(cur[i]) + cur[i + 1:]\n",
    "                yield cur[:i] + plus_p(cur[i]) + cur[i + 1:]\n",
    "\n",
    "        q = deque()\n",
    "        visited = {'0000'}\n",
    "        q.append('0000')\n",
    "        step = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                if cur == target:\n",
    "                    return step\n",
    "                for lj in lingju(cur):\n",
    "                    if lj not in visited and cur not in deadends:\n",
    "                        visited.add(lj)\n",
    "                        q.append(lj)\n",
    "            step += 1\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends, target):\n",
    "        # 初始和目标状态都作为字符串处理\n",
    "        if \"0000\" in deadends:\n",
    "            return -1\n",
    "        deadends = set(deadends)\n",
    "\n",
    "        def get_state(s):\n",
    "            states = []\n",
    "            for i in range(4):\n",
    "                digit = int(s[i])\n",
    "                for d in [-1, 1]:\n",
    "                    new_digit = (digit + d) % 10\n",
    "                    states.append(s[:i] + str(new_digit) + s[i+1:])\n",
    "            return states\n",
    "\n",
    "        def bfs(deadends, target):\n",
    "            visited = set()\n",
    "            queue = deque([\"0000\"])\n",
    "            level = 0\n",
    "            while queue:\n",
    "                for _ in range(len(queue)):\n",
    "                    mat = queue.popleft()\n",
    "                    if mat == target:\n",
    "                        return level\n",
    "                    if mat in deadends:\n",
    "                        continue\n",
    "                    states = get_state(mat)\n",
    "                    for state in states:\n",
    "                        if state not in deadends and state not in visited:\n",
    "                            queue.append(state)\n",
    "                            visited.add(state)\n",
    "                level += 1\n",
    "            return -1\n",
    "\n",
    "        return bfs(deadends, target)\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def openLock(self, deadends: List[str], target: str) -> int:\n",
    "        if target == \"0000\":\n",
    "            return 0\n",
    "\n",
    "        dead = set(deadends)\n",
    "        if \"0000\" in dead:\n",
    "            return -1\n",
    "        \n",
    "        def num_prev(x: str) -> str:\n",
    "            return \"9\" if x == \"0\" else str(int(x) - 1)\n",
    "        \n",
    "        def num_succ(x: str) -> str:\n",
    "            return \"0\" if x == \"9\" else str(int(x) + 1)\n",
    "        \n",
    "        # 枚举 status 通过一次旋转得到的数字\n",
    "        def get(status: str) -> Generator[str, None, None]:\n",
    "            s = list(status)\n",
    "            for i in range(4):\n",
    "                num = s[i]\n",
    "                s[i] = num_prev(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = num_succ(num)\n",
    "                yield \"\".join(s)\n",
    "                s[i] = num\n",
    "\n",
    "        q = deque([(\"0000\", 0)])\n",
    "        seen = set(\"0000\")\n",
    "        while q:\n",
    "            status, step = q.popleft()\n",
    "            for next_status in get(status):\n",
    "                if next_status not in seen and next_status not in dead:\n",
    "                    if next_status == target:\n",
    "                        return step + 1\n",
    "                    q.append((next_status, step + 1))\n",
    "                    seen.add(next_status)\n",
    "        \n",
    "        return -1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
